//
// Created by DengLibin on 2019/1/23 0023.
//
#include <iostream>
#include <vector>
using  namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
/**
 * vector 求和
 * @param v
 * @return
 */
int sum_vector(vector<int> & v){
    int sum = 0;
    for(int x : v){
        sum += x;
    }
    return sum;
}
void show_vector(vector<int> & v){
    for(int x : v){
        cout << x<<",";
    }
    cout <<endl;
}

/**
       是否是叶子节点
   */
bool isYeZi_74(TreeNode * root){
    if(root == NULL){
        return false;
    }
    return root->left == NULL && root->right == NULL;
}
void getSum(TreeNode * root, vector<int > v, int targetSum, vector<vector<int>> & rv){
    if(root == NULL){
        return;
    }
    if(isYeZi_74(root)){
        //当累加到叶子节点时判断是否和指定的和相等
        if(sum_vector(v)+root->val  == targetSum){
            v.push_back(root->val);
            show_vector(v);
            rv.push_back(v);
        }
        return;
    }
    vector<int > v1 =v;
    v1.push_back(root->val);
    getSum(root->left, v1, targetSum, rv);
    vector<int > v2=v;
    v2.push_back(root->val);
    getSum(root->right, v2, targetSum, rv);

}
/**
 * 是否存在路径总和等于给定的值
 * @param root
 * @param sum
 * @return
 */
vector<vector<int >> hasPathSum_74(TreeNode* root, int sum) {
    vector<int >v;
    vector<vector<int >> rv;
    if(root == NULL){
        return rv;
    }
    getSum(root,v,sum,rv);
    return rv;
}
int main74(){
    TreeNode node1 = {3};
    TreeNode node2 = {9};
    TreeNode node3 = {20};
    node1.left = &node2;
    node1.right = &node3;
    TreeNode node5 = {7};
    TreeNode node6 = {15};
    node3.left = &node5;
    node3.right = &node6;

    hasPathSum_74(&node1,30);
    return 0;
}
